package btree.base;

/**
 * 非常经典的基于DFS求二叉树的深度
 */
public class TreeDepth {

    /* ===== 1. 节点定义 ===== */
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
    }

    /* ===== 2. 递归求最大深度 =====
       空树深度为 0；否则为 1 + max(左子树深度, 右子树深度) */
    public static int maxDepth(Node root) {
        if (root == null) return 0;
        int leftDepth  = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return 1 + Math.max(leftDepth, rightDepth);
    }

    /* ===== 3. 构造示例树并测试 =====
     *         1
     *       /   \
     *      2     3
     *     / \
     *    4   5
     * 最大深度 = 3
     */
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        int depth = maxDepth(root);
        System.out.println("Max depth = " + depth);   // 输出 3
    }
}
